import java.util.Arrays;

public class NM {
    //归并排序的非递归实现；
    public static void guiBing(int[] array){
        int gap=1;
        while(gap<array.length){
            for(int i=0;i< array.length;i=i+2*gap){
                int left=i;
                int mid=left+gap-1;
                if(mid>= array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if(right>= array.length){
                    right= array.length-1;
                }
                heBing(array,left,mid,right);
            }
            gap*=2;
        }
    }
    public static void heBing(int[] array,int left,int mid,int right){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int[] temp=new int[right-left+1];
        int k=0;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                temp[k++]=array[s1++];
            }else{
                temp[k++]=array[s2++];
            }
        }
        while(s1<=e1){
            temp[k++]=array[s1++];
        }
        while(s2<=e2){
            temp[k++]=array[s2++];
        }
        for(int i=0;i<k;i++){
            array[i+left]=temp[i];
        }
    }
    public static void main(String[] args){
        int[] array={13,34,45,22,11,22,1,2,4,2};
        guiBing(array);
        System.out.println(Arrays.toString(array));
    }
}
